class Solution:
    def getMoneyAmount(self, n: int) -> int:
        def getMoney(start, end, cache):
            if (start, end) in cache:
                return cache[(start,end)]
            if start == end:
                cache[(start, end)] = 0
                return 0
            if start == end - 1:
                cache[(start, end)] = start
                return start
            if start > end:
                return 0
            minLen = n * n
            for i in range((start+end)//2, end):
                if start >= i or end <= i:
                    continue
                left = getMoney(start, i - 1, cache)
                right = getMoney(i + 1, end, cache)
                minLen = min(max(left, right) + i, minLen)
            cache[(start, end)] = minLen
            return minLen

        return getMoney(1, n, {})


if __name__ == '__main__':
    so = Solution()
    n = 10
    r = so.getMoneyAmount(n)
    print(r)
